﻿#include "header.h"

/*

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
 /  \
15   7

*/

class Solution {
public:
	TreeNode * buildTree(vector<int> &inorder, vector<int> &postorder)
	{
		int len = inorder.size();
		if (len == 0) return nullptr;
		return findRoot(inorder, 0, len - 1, postorder, 0, len - 1);
	}
	TreeNode * findRoot(vector<int> &inorder, int inStart, int inEnd, vector<int> &postorder, int pStart, int pEnd)
	{
		if (inStart > inEnd)
			return nullptr;
		TreeNode *root = new TreeNode(postorder[pEnd]);
		int lcNum = 0;
		for (int i = inStart; inorder[i] != root->val; ++i)
		{
			++lcNum;
		}
		root->left = findRoot(inorder, inStart, inStart + lcNum - 1, postorder, pStart, pStart + lcNum - 1);
		root->right = findRoot(inorder, inStart + lcNum + 1, inEnd, postorder, pStart + lcNum, pEnd - 1);
		return root;
	}
};